package Algorithm.String;

//https://leetcode-cn.com/problems/repeated-string-match/
//686. 重复叠加字符串匹配
public class Leetcode686_重复叠加字符串匹配 {
    class Solution {
        public int repeatedStringMatch(String a, String b) {
            int ans = 0;
            StringBuilder builder = new StringBuilder();

            while(builder.length() < b.length()){
                builder.append(a);
                ans++;
            }

            builder.append(a);

            int index = KMP(builder.toString(), b);

            if(index==-1){
                return -1;
            }

            return index + b.length() <= a.length() * ans ? ans : ans+1;
        }

        /**
         * KMP 算法，自己实现了一遍，KMP 算法的核心就是利用上之前匹配过的信息
         *
         * @param target
         * @param partten
         * @return
         */
        public int KMP(String target, String partten){
            target = target;
            partten = partten;

            //首先 next 数组表示在 i 位置， 在0-i位置的partten子串中，前缀和后缀相同的长度为 next[i]
            //并且这样子，next[i] 也正好是当匹配不上时，需要跳转的下标
            int[] next = new int[partten.length()];
            int j = 0;
            for(int i=1;i<partten.length();i++){
                while(partten.charAt(i) != partten.charAt(j) && j>0){
                    //同时要注意，当位置匹配不上时，我们需要的是当前位置的前一个位置需要跳转的下标
                    //因为当前位置已经是匹配不上的，如果是 j = next[j]，新的 next[j] 还是匹配不上的
                    j = next[j-1];
                }

                if(partten.charAt(i) == partten.charAt(j)){
                    j++;
                }

                next[i] = j;
            }

            int k=0;
            for(int i=0;i<target.length();i++){
                while(target.charAt(i) != partten.charAt(k) && k>0){
                    //同时要注意，当位置匹配不上时，我们需要的是当前位置的前一个位置需要跳转的下标
                    //因为当前位置已经是匹配不上的，如果是 k = next[k]，新的 next[k] 还是匹配不上的
                    k = next[k-1];
                }

                if(target.charAt(i) == partten.charAt(k)){
                    k++;
                }

                if(k==partten.length()){
                    return i-(k-1);
                }
            }

            return -1;
        }
    }
}
